package LearnAlgorithm.c_递归and查找排序;

public class p查找乱序数组的逆序对个数 {
	public static int niXu = 0;
	public static int[] helper = null;
	public static void main(String[] args) {
		int[] arr = new int[] {9,8,7,6,5};
		helper = new int[arr.length];
		long before = System.currentTimeMillis();
		mergeSort(arr, 0, arr.length - 1);
		util.Util.duration(before);
		System.out.println(niXu);
		niXu = 0;
		int[] arr2 = new int[] {9,8,7,6,5};
		long before2 = System.currentTimeMillis();
		mergeByCountMyself(arr2, 0, arr2.length - 1);
		util.Util.duration(before2);
		System.out.println(niXu);
//		for (int i = 0; i < arr.length; i++) {
//			System.out.print(arr[i] + " ");
//		}
		
	}
	
	public static void mergeSort(int[] arr, int p, int r) {
		if (p < r) {
			int mid = p + ((r - p) >>> 1);
			mergeSort(arr, p, mid);
			mergeSort(arr, mid + 1, r);
			merge(arr, p, r, mid);
		}
	}
	
	public static void mergeByCountMyself(int[] arr, int p, int r) {
		if (p < r) {
			int mid = p + ((r - p) >>> 1);
			mergeByCountMyself(arr, p, mid);
			mergeByCountMyself(arr, mid + 1, r);
			mergeByCount(arr, p, r, mid);
		}
	}
	
	public static void mergeByCount(int[] arr, int p, int r, int mid) {//这是自己的思想，分治，然后比对；不会出现重复比对的现象
		for (int right = mid + 1; right <= r; right++) {
			int left = p;
			while (left < mid + 1) {//注意这里left < mid + 1,也就是right的初始值
				if (arr[left] > arr[right]) {
					left++;
					niXu++;
				} else if (arr[left] <= arr[right]) {
					left++;
				}
			}
		}
		
	}
	
	public static void merge(int[] arr, int p, int r, int mid) {//每一次被递归的同时被排序，但是随着每一次排序，niXu都会正常的加上理所应当的次数，这是老师的思想
		copy(arr, helper, p, r - p + 1);
		int left = p;
		int right = mid + 1;
		int current = p;
		while (left <= mid && right <= r) {
			if (helper[left] <= helper[right]) {
				arr[current] = helper[left];
				current++;
				left++;
			} else {
				arr[current] = helper[right];
				current++;
				right++;
				niXu += mid - left + 1;//右边比左边小
			}
		}
		while (left <= mid) {
			arr[current] = helper[left];
			current++;
			left++;
		}
	}
	
	public static void copy(int[] arr,int[] helper, int p, int r) {
		for (int i = 0; i < r; i++) {
			helper[p] = arr[p];
			p++;
		}
	}
}
